#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define M 4
#define N 4
#define Max 16

typedef struct
{
    int row;   //行号
    int col;   //列号
    int value; //值
} TupNode;

typedef struct
{
    int row_nums; //行数
    int col_nums; //列数
    int nums;     //非零元素个数
    TupNode data[Max * Max];
} TSMatrix;

void CreatMat(TSMatrix &t, int A[M][N], int r, int c) //生成三元组表
{
    int i, j;
    t.row_nums = M;
    t.col_nums = N;
    t.nums = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (A[i][j] != 0)
            {
                t.data[t.nums].row = i;
                t.data[t.nums].col = j;
                t.data[t.nums].value = A[i][j];
                t.nums++;
            }
        }
    }
}

void TranTat(TSMatrix t, TSMatrix &tb) //稀疏矩阵的转置
{
    int k, k1 = 0, v;
    tb.row_nums = t.col_nums;
    tb.col_nums = t.row_nums;
    tb.nums = t.nums;
    if (t.nums != 0)
    {
        for (v = 0; v < t.col_nums; v++)
            for (k = 0; k < t.nums; k++)
                if (t.data[k].col == v)
                {
                    tb.data[k1].row = t.data[k].col;
                    tb.data[k1].col = t.data[k].row;
                    tb.data[k1].value = t.data[k].value;
                    k1++;
                }
    }
}

void DispMat(TSMatrix t)
{
    int k;
    if (t.nums <= 0)
        return;
    printf("行号\t列号\t值\n");
    for (k = 0; k < t.nums; k++)
        printf("%d\t%d\t%d\t\n", t.data[k].row, t.data[k].col, t.data[k].value);
}

TSMatrix addTSMatrix(TSMatrix A, TSMatrix B) //三元组相加
{
    TSMatrix ret;
    ret.row_nums = A.row_nums;
    ret.col_nums = A.col_nums;
    ret.nums = 0;
    int i = 0, j = 0;
    while (i < A.nums && j < B.nums)
    {
        if (A.data[i].row < B.data[j].row)
        {
            ret.data[ret.nums].row = A.data[i].row;
            ret.data[ret.nums].col = A.data[i].col;
            ret.data[ret.nums].value = A.data[i].value;
            i++;
            ret.nums++;
        }
        else if (A.data[i].row == B.data[j].row)
        {
            if (A.data[i].col < B.data[j].col)
            {
                ret.data[ret.nums].row = A.data[i].row;
                ret.data[ret.nums].col = A.data[i].col;
                ret.data[ret.nums].value = A.data[i].value;
                i++;
                ret.nums++;
            }
            else if (A.data[i].col > B.data[j].col)
            {
                ret.data[ret.nums].row = A.data[j].row;
                ret.data[ret.nums].col = A.data[j].col;
                ret.data[ret.nums].value = A.data[j].value;
                j++;
                ret.nums++;
            }
            else
            {
                if (B.data[j].value + A.data[i].value != 0)
                {
                    ret.data[ret.nums].row = A.data[i].row;
                    ret.data[ret.nums].col = A.data[i].col;
                    ret.data[ret.nums].value = A.data[i].value + B.data[j].value;
                    ret.nums++;
                }
                i++;
                j++;
            }
        }
        else
        {
            ret.data[ret.nums].row = B.data[j].row;
            ret.data[ret.nums].col = B.data[j].col;
            ret.data[ret.nums].value = B.data[j].value;
            j++;
            ret.nums++;
        }
    }
    while (i < A.nums)
    {
        ret.data[ret.nums].row = A.data[i].row;
        ret.data[ret.nums].col = A.data[i].col;
        ret.data[ret.nums].value = A.data[i].value;
        i++;
        ret.nums++;
    }
    while (j < B.nums)
    {
        ret.data[ret.nums].row = B.data[j].row;
        ret.data[ret.nums].col = B.data[j].col;
        ret.data[ret.nums].value = B.data[j].value;
        j++;
        ret.nums++;
    }
    return ret;
}

TSMatrix multiplyMatrix(int A[M][N], int B[N][M])
{
    TSMatrix ret;
    ret.row_nums = M;
    ret.col_nums = N;
    ret.nums = 0;
    int i = 0, j = 0;
    int sum[M][N];
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            sum[i][j] = 0;
            for (int k = 0; k < M; ++k)
            {
                sum[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    CreatMat(ret, sum, M, N);
    return ret;
}

int main()
{
    int A[M][N] = {{1, 0, 3, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 1, 1}};
    int B[M][N] = {{3, 0, 0, 0}, {0, 4, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 2}};

    TSMatrix t1, t2;
    CreatMat(t1, A, M, N);
    CreatMat(t2, B, M, N);
    printf("稀疏矩阵A的三元组表为：\n");
    DispMat(t1);
    // printf("稀疏矩阵B的三元组表为：\n");
    //  DispMat(t2);

    //矩阵转置
    TSMatrix t3;
    TranTat(t1, t3);
    printf("稀疏矩阵A转置后的三元组表为：\n");
    DispMat(t3);

    //矩阵A+矩阵B
    TSMatrix ret = addTSMatrix(t1, t2);
    printf("A+B的结果为：\n");
    DispMat(ret);

    //矩阵A*B
    TSMatrix mutply = multiplyMatrix(A, B);
    printf("A*B的结果为：\n");
    DispMat(mutply);

    return 0;
}